#include <string>
#include <vector>
using namespace std;
bool withEnd(string s1, string s2) {
  if (s1.size() < s2.size())
    return false;
  int r1 = s1.size() - 1;
  int r2 = s2.size() - 1;
  while (r2 >= 0) {
    if (s1[r1--] != s2[r2--]) {
      return false;
    }
  }
  return true;
}
bool wordBreak(string s, vector<string> &wordDict) {
  vector<int> dp(s.size() + 1);
  dp[0] = 1;
  for (int i = 1; i <= s.size(); ++i) {
    for (auto &word : wordDict) {
      if (withEnd(s.substr(0, i), word)) {
        dp[i] = dp[i - word.size()];
        if (dp[i] == 1)
          break;
      }
    }
  }
  return dp[s.size()] == 1;
}